/*
 * Lista.h
 *
 *  Created on: 18/04/2011
 *      Author: Jonathan
 */
#include "Nodo.h"
#include "IteradorLista.h"
#include "Comparador.h"
#ifndef LISTA_H_
#define LISTA_H_

template<class C> class Lista {

private:
	/*primer nodo */
	Nodo<C> *raiz;
	/* cantidad de nodos */
	int cant;
	/* Comparador que utiliza para ordenar los elementos */
	Comparador<C> * comparador;

public:
	Lista() {
		raiz = NULL;
		cant = 0;
		this->comparador = new ComparadorConstante<C>;
	}

	/**
	 * Constructor con comparador.
	 * Una vez que se pasa el puntero con el comparador, la lista toma el control del puntero.
	 * @param comparador
	 */
	Lista(Comparador<C> * comparador) {
		raiz = NULL;
		cant = 0;
		this->comparador = comparador;
	}
	void copiarLista(const Lista<C> & listaACopiar) {
		delete this->comparador;
		this->comparador = listaACopiar.comparador->getNuevaInstancia();
		if (listaACopiar.cant > 0) {
			Nodo<C> **posDondeCopiar = &raiz;
			Nodo<C> *posDesdeCopiar = listaACopiar.raiz;
			while (posDesdeCopiar) {
				*posDondeCopiar = new Nodo<C> (posDesdeCopiar->getDato());
				posDondeCopiar = &(**posDondeCopiar).getSiguiente();
				posDesdeCopiar = posDesdeCopiar->getSiguiente();
			}
		}
		this->cant = listaACopiar.cant;
	}

	Lista(const Lista<C> & listaACopiar) {
		this->clear();
		copiarLista(listaACopiar);
	}

	void operator =(Lista & listaAAsignar) {
		this->clear();
		copiarLista(listaAAsignar);
	}

	void add(C elemento) {

		Nodo<C> ** posicion = &raiz;
		Nodo<C> * nodoAux;
		if (*posicion) {
			while (*posicion != NULL && ((*posicion)->sig != NULL
					&& comparador->comparar((*posicion)->sig->getDato(),
							elemento) != MAYOR)) {
				posicion = &((*posicion)->sig);
			}
			if (*posicion != NULL) {
				if (comparador->comparar((*posicion)->getDato(), elemento) == MAYOR ){
					nodoAux = *posicion;
					*posicion = new Nodo<C> (elemento);
					(*posicion)->sig = nodoAux;
				} else {
					nodoAux = new Nodo<C> (elemento);
					nodoAux->sig = (*posicion)->sig;
					(*posicion)->sig = nodoAux;
				}
			} else {
				(*posicion)= new Nodo<C>(elemento);
			}
		} else {
			(*posicion) = new Nodo<C>(elemento);
		}
		cant++;
	}

	void deleteAllOcurrences(C elemento) {
		borrarRec(elemento, this->raiz);
	}

	bool isEmpty() {
		return raiz == 0;
	}

	bool exist(C elemento) {
		return existerec(elemento, this->raiz);
	}

	virtual ~Lista() {
		destructRec(this->raiz);
		delete this->comparador;
	}

	int size() {
		return cant;
	}

	C getAt(int posicion) {
		return buscarRec(0, posicion, raiz);
	}

	void clear() {
		destructRec(raiz);
		this->raiz = NULL;
		cant = 0;
	}

	/**
	 * pre : ninguna.
	 * post: devuelve una nueva instancia de iterador localizado en el
	 *       comienzo de la lista.
	 *
	 */
	IteradorLista<C> iterador() {

		IteradorLista<C> unIterador(this);
		return unIterador;
	}

	friend class IteradorLista<C> ;
private:
	void borrarRec(C & elemento, Nodo<C> *& nodo) {
		if (nodo) {
			if (nodo->getDato() == elemento) {
				Nodo<C> *aux = nodo;
				nodo = nodo->getSiguiente();
				delete aux;
				cant--;
				borrarRec(elemento, nodo);
			} else {
				borrarRec(elemento, nodo->getSiguiente());
			}
		}

	}

	void altaRec(C & elemento, Nodo<C> *& nodoAnterior, Nodo<C> *& nodoActual) {

	}

		bool existerec(const C & elemento, Nodo<C> *& nodo) {
			if (nodo) {
				if (nodo->getDato() == elemento) {
					return true;
				} else
					return existerec(elemento, nodo->getSiguiente());
			} else
				return false;
		}

		void destructRec(Nodo<C> *& nodo) {
			if (nodo) {
				if (nodo->getSiguiente()) {
					destructRec(nodo->getSiguiente());
				}
				delete nodo;
			}
		}

		C buscarRec(int posicionActual, int posicionBuscada, Nodo<C> * nodo) {
			C salidaNula;
			if (nodo) {
				if (posicionActual == posicionBuscada) {
					return nodo->getDato();
				} else {
					return buscarRec(posicionActual + 1, posicionBuscada,
							nodo->getSiguiente());
				}
			} else {
				return salidaNula;
			}
		}

	}
	;
#endif /* LISCA_H_ */
